package com.aqie.easy.binaryTree;

import com.aqie.easy.structure.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 872 y叶子相似的树
 * 深度优先搜索  栈
 * todo
 */
public class LeafSimilar {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        // 1. 获取二叉树叶值节点
        // 2. 比较两个list是否相等

        List<Integer> leaves1 = new ArrayList();
        List<Integer> leaves2 = new ArrayList();
        dfs(root1, leaves1);
        dfs(root2, leaves2);
        return leaves1.equals(leaves2);
    }

    private void dfs(TreeNode node, List<Integer> leafValues) {
        if (node != null) {
            if (node.left == null && node.right == null)
                leafValues.add(node.val);
            dfs(node.left, leafValues);
            dfs(node.right, leafValues);
        }

    }
}
